package chapter02;

public class Partition86 {
    /**
     * 将链表分为两个区域 1.<x   2.>=x
     * 指针指向两个区域的头和尾
     * lessHead=null  otherHead=null
     * lessTail=null  otherTail=null
     * 遍历链表
     * 1.如果当前节点值小于x，将当前节点接在lessTail上
     * 2.否则 将当前节点接在otherTail上
     * 将两个区域连接  返回头指针
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
    public ListNode partition(ListNode head, int x) {
        ListNode lessHead=null;
        ListNode lessTail=null;
        ListNode otherHead=null;
        ListNode otherTail=null;
        while (head!=null){
            if(head.val<x){
                if(lessHead==null){
                    lessHead=lessTail=head;
                }else{
                    lessTail.next=head;
                    lessTail=head;
                }
            }else{
                if(otherHead==null){
                    otherHead=otherTail=head;
                }else{
                    otherTail.next=head;
                    otherTail=head;
                }
            }
            head=head.next;
        }
        if(lessHead==null){
            if(otherHead==null){
                return null;
            }else{
                otherTail.next=null;
                return otherHead;
            }
        }else{
            lessTail.next=null;
            if(otherHead!=null){
                otherTail.next=null;
                lessTail.next=otherHead;

            }
            return lessHead;
        }
    }
}
